home *** CD-ROM | disk | FTP | other *** search
/ CU Amiga Super CD-ROM 17 / CU Amiga Magazine's Super CD-ROM 17 (1997)(EMAP Images)(GB)[!][issue 1997-12].iso / CUCD / Programming / DiceSource / lib / extra / wildcard.c < prev   
C/C++ Source or Header  |  1997-09-09  |  8KB  |  377 lines
  1.  
  2. /*
  3.  *  WILDCARD.C        AmigaDos wildcard comparator
  4.  *
  5.  *            WARNING:  Uses *Lots* of stack
  6.  *
  7.  *
  8.  *    (c)Copyright 1992-1997 Obvious Implementations Corp.  Redistribution and
  9.  *    use is allowed under the terms of the DICE-LICENSE FILE,
  10.  *    DICE-LICENSE.TXT.
  11.  */
  12.  
  13. #define _EXTRA_WILDCARD_C
  14. #include <stdio.h>
  15. #include <stdlib.h>
  16. #include <string.h>
  17. #include <errno.h>
  18. #include <lib/misc.h>
  19.  
  20. #define SetWildStack    _SetWildStack
  21. #define CompWild    _CompWild
  22. #define ParseWild   _ParseWild
  23. #define FreeWild    _FreeWild
  24.  
  25. /*
  26.  *  Example:    #(a|b|c)xx  consts of:
  27.  *
  28.  *    masternode(#), wn_Next = xx
  29.  *               wn_Sub  = (a|b|c)
  30.  *
  31.  *    (a|b|c) wn_Next ->  a, wn_Next = NULL, wn_Sib = b
  32.  *                b, wn_Next = NULL, wn_Sib = c
  33.  *                c, wn_Next = NULL, wn_Sib = NULL
  34.  *
  35.  *  Etc...
  36.  *
  37.  *  The most complexity occurs when dealing with '#' ... this could
  38.  *  probably be made more efficient.  Basically, we run through all
  39.  *  possible repeats from N to none at all.  For example, if the pattern
  40.  *  is #?x  then we try ????x ???x ??x ?x, and x.  The number of repeats
  41.  *  we try is currently STUPIDLY set to the length of the name remaining
  42.  *  since that is the worst case.
  43.  *
  44.  *  Note that this algorithm correctly handles extremely complex patterns
  45.  *  like:   #(a|b#?|c).o
  46.  */
  47.  
  48. typedef struct WildNode {
  49.     struct WildNode *wn_Next;    /*  next wild node (append to current) */
  50.     struct WildNode *wn_Sib;    /*  sibling wild node (a|b|c|d)        */
  51.     struct WildNode *wn_Sub;    /*  sub wildnode #(a|b|c)              */
  52.     struct WildNode *wn_Cont;    /*  used at Compare time           */
  53.     const char *wn_Pat;     /*  patterns not containing | or #     */
  54.     short wn_PatLen;        /*  length of pattern        */
  55.     short wn_Type;        /*  '|', '#', or 0          */
  56.     short wn_Repeat;        /*  # of repeats (for '#')  */
  57. } WildNode;
  58.  
  59. void SetWildStack(long);                       /*  global  */
  60. WildNode *ParseWild(const char *, short);
  61. int CompWild(const char *, WildNode *, WildNode *);
  62. void FreeWild(WildNode *);
  63.  
  64. WildNode *ParseSubWild(const char *, short);    /*  local   */
  65. int extinpat(const char *, int);
  66. int extonepat(const char *, int);
  67.  
  68.  
  69. /*
  70.  *  Parse the structure & run
  71.  */
  72.  
  73. static char *BotStack;
  74.  
  75. WildNode *
  76. ParseWild(pat, patlen)
  77. const char *pat;
  78. short patlen;
  79. {
  80.     short i;
  81.     WildNode *wn = NULL;
  82.     WildNode **wnext = &wn;
  83.  
  84.     if (patlen == 0)
  85.     return(NULL);
  86.  
  87.     while (i = extinpat(pat, patlen)) {
  88.     *wnext = ParseSubWild(pat, i);
  89.  
  90.     wnext = &(*wnext)->wn_Sib;
  91.  
  92.     pat += i;
  93.     patlen -= i;
  94.     if (patlen && *pat == '|') {
  95.         ++pat;
  96.         --patlen;
  97.     }
  98.     }
  99.     return(wn);
  100. }
  101.  
  102. static WildNode *
  103. ParseSubWild(pat, patlen)
  104. const char *pat;
  105. short patlen;
  106. {
  107.     WildNode *wn;
  108.  
  109.     short i;
  110.  
  111.     if (patlen == 0)
  112.     return(NULL);
  113.  
  114.     wn = calloc(sizeof(WildNode), 1);
  115.  
  116.     for (i = 0; i < patlen; ++i) {
  117.     if (pat[i] == '#' || pat[i] == '(')
  118.         break;
  119.     if (pat[i] == '\'')
  120.         ++i;
  121.     }
  122.  
  123.     if (i) {
  124.     wn->wn_Pat = pat;
  125.     wn->wn_PatLen = i;
  126.     wn->wn_Next = ParseSubWild(pat + i, patlen - i);
  127.     } else if (*pat == '#') {
  128.     ++pat;
  129.     --patlen;
  130.     i = extonepat(pat, patlen);
  131.     wn->wn_Sub  = ParseWild(pat, i);
  132.     wn->wn_Type = '#';
  133.     wn->wn_Next = ParseSubWild(pat + i, patlen - i);
  134.     } else if (*pat == '(') {
  135.     i = extonepat(pat, patlen);
  136.     wn->wn_Sub = ParseWild(pat + 1, i - 2);
  137.     wn->wn_Type = 0;
  138.     wn->wn_Next = ParseSubWild(pat + i, patlen - i);
  139.     }
  140.     return(wn);
  141. }
  142.  
  143. void
  144. FreeWild(wn)
  145. WildNode *wn;
  146. {
  147.     if (wn) {
  148.     if (wn->wn_Sib)
  149.         FreeWild(wn->wn_Sib);
  150.     if (wn->wn_Next)
  151.         FreeWild(wn->wn_Next);
  152.     if (wn->wn_Sub)
  153.         FreeWild(wn->wn_Sub);
  154.     free(wn);
  155.     }
  156. }
  157.  
  158. void
  159. SetWildStack(n)
  160. long n;
  161. {
  162.     BotStack = (char *)&n - n;
  163. }
  164.  
  165. /*
  166.  *  CompWild().     Pretty straight forward except for '#'.
  167.  *
  168.  *  The 'cont' field is a linked string of nodes that specify patterns
  169.  *  that must be successfully compared after the current pattern, 'wn',
  170.  *  compares successfully.  When we are dealing with repeats of a
  171.  *  pattern, such as #(a|b).o, then the 'cont' field is used to specify
  172.  *  that (a|b) should be repeated wn_Repeat times.
  173.  *
  174.  *  A further complication occurs with: #(a|b#?).o, where we have a
  175.  *  nested repeat loop.  In this case as 'cont' is scanned ONLY the
  176.  *  top repeat loop is decremented by the 'cont' code.  The inner loop
  177.  *  will be decremented by the '#' code.  Thus, when we skip to the
  178.  *  next 'cont' we must skip any nodes with non-zero wn_Repeat
  179.  *
  180.  *  I am not entirely certain that I've done it properly, the code is
  181.  *  complex.
  182.  */
  183.  
  184. CompWild(name, wn, cont)
  185. const char *name;
  186. WildNode *wn;
  187. WildNode *cont;
  188. {
  189.     {
  190.     char x;
  191.  
  192.     if (&x < BotStack) {
  193.         errno = ESTACK;
  194.         return(-1);
  195.     }
  196.     }
  197. top:
  198.     if (wn == NULL) {
  199.     if (cont) {
  200.         if (cont->wn_Repeat) {
  201.         if (--cont->wn_Repeat) {
  202.             wn = cont->wn_Sub;
  203.             cont = cont;
  204.         } else {
  205.             wn = cont->wn_Sub;
  206.             cont = cont->wn_Cont;
  207.             while (cont && cont->wn_Repeat)
  208.             cont = cont->wn_Cont;
  209.         }
  210.         goto top;
  211.         } else {
  212.         wn = cont;
  213.         cont = cont->wn_Cont;
  214.         while (cont && cont->wn_Repeat)
  215.             cont = cont->wn_Cont;
  216.         goto top;
  217.         /*return(CompWild(name, cont, cont->wn_Cont));*/
  218.         }
  219.     }
  220.     if (*name)
  221.         return(-1);
  222.     return(0);
  223.     }
  224.     /*printf("foo %08lx (%d)%.*s\n", wn, wn->wn_PatLen, wn->wn_PatLen, wn->wn_Pat);*/
  225.     if (wn->wn_PatLen) {
  226.     const char *pat = wn->wn_Pat;
  227.     const char *oname = name;
  228.     short patlen;
  229.  
  230.     for (patlen = wn->wn_PatLen; patlen > 0; --patlen, ++pat) {
  231.         switch(*pat) {
  232.         case '%':
  233.         break;
  234.         case '?':
  235.         if (*name == 0)
  236.             patlen = 0;     /*    fail    */
  237.         ++name;
  238.         break;
  239.         case '\'':
  240.         ++pat;
  241.         --patlen;
  242.         /* fall through */
  243.         default:
  244.         {
  245.             char c1 = *name;
  246.             char c2 = *pat;
  247.             if (c1 != c2) {
  248.             if (c1 >= 'a' && c1 <= 'z')
  249.                 c1 += 'A' - 'a';
  250.             if (c2 >= 'a' && c2 <= 'z')
  251.                 c2 += 'A' - 'a';
  252.             if (c1 != c2)
  253.                 patlen = 0;     /*    fail    */
  254.             }
  255.         }
  256.         ++name;
  257.         break;
  258.         }
  259.     }
  260.     if (patlen < 0 || CompWild(name, wn->wn_Next, cont) < 0) {
  261.         if (wn->wn_Sib)
  262.         return(CompWild(oname, wn->wn_Sib, cont));
  263.         return(-1);
  264.     }
  265.     return(0);
  266.     }
  267.     {
  268.     WildNode *next = wn->wn_Next;
  269.  
  270.     if (next) {
  271.         next->wn_Cont = cont;
  272.         cont = next;
  273.     }
  274.     if (wn->wn_Type == '#') {
  275.         short i = strlen(name);
  276.  
  277.         while (i > 0) {
  278.         wn->wn_Cont = cont;
  279.         wn->wn_Repeat = i;
  280.         if (CompWild(name, NULL, wn) >= 0) {
  281.             wn->wn_Repeat = 0;
  282.             return(0);
  283.         }
  284.         --i;
  285.         }
  286.         wn->wn_Repeat = 0;
  287.         if (CompWild(name, NULL, cont) < 0) {
  288.         if (wn->wn_Sib) {
  289.             wn = wn->wn_Sib;
  290.             goto top;
  291.         }
  292.         return(-1);
  293.         }
  294.         return(0);
  295.     } else {
  296.         if (CompWild(name, wn->wn_Sub, cont) < 0) {
  297.         if (wn->wn_Sib == NULL)
  298.             return(-1);
  299.         wn = wn->wn_Sib;
  300.         goto top;
  301.         /*return(CompWild(name, wn->wn_Sib, cont));*/
  302.         }
  303.         return(0);
  304.     }
  305.     }
  306. }
  307.  
  308.  
  309. static int
  310. extonepat(pat, patlen)
  311. const char *pat;
  312. int patlen;
  313. {
  314.     if (patlen <= 0) {
  315.     printf("PATLEN BAD %d\n", patlen);
  316.     return(0);
  317.     }
  318.     switch(*pat) {
  319.     case '?':
  320.     case '%':
  321.     return(1);
  322.     case '#':
  323.     return(1 + extonepat(pat + 1, patlen - 1));
  324.     case '|':
  325.     puts("extone, unexpected '|'");
  326.     return(0);
  327.     case '(':
  328.     {
  329.         short pcnt = 0;
  330.         short i = 0;
  331.  
  332.         while (patlen) {
  333.         ++i;
  334.         if (*pat == '(')
  335.             ++pcnt;
  336.         if (*pat == ')' && --pcnt == 0)
  337.             return(i);
  338.         ++pat;
  339.         --patlen;
  340.         }
  341.     }
  342.     puts("unexpected EOF looking for ')'");
  343.     return(0);
  344.     case '\'':
  345.     if (patlen < 2) {
  346.         puts("extone, unexpected EOF at '");
  347.         return(0);
  348.     }
  349.     return(2);
  350.     default:
  351.     return(1);
  352.     }
  353.     /* not reached */
  354. }
  355.  
  356.  
  357. static int
  358. extinpat(pat, patlen)
  359. const char *pat;
  360. int patlen;
  361. {
  362.     int i;
  363.     short paren = 0;
  364.  
  365.     for (i = 0; i < patlen; ++i) {
  366.     if (pat[i] == '(')
  367.         ++paren;
  368.     if (pat[i] == ')' && --paren < 0)
  369.         return(i);
  370.     if (pat[i] == '|' && paren == 0)
  371.         return(i);
  372.     }
  373.     return(i);
  374. }
  375.  
  376.  
  377.